package practice1_100;

import java.util.*;

public class Meituan {
    public boolean hasCycle(ListNode head) {
            ListNode slow=head;
            ListNode fast=head;
            while (fast.next!=null&&fast.next.next!=null){
                slow=slow.next;
                fast=fast.next.next;
                if(slow==fast){
                    return true;
                }
            }
            return false;
    }

    public static void main(String[] args) {
       boolean a= checkValidString("((*))(())");
//        "".ch
    }
    public static boolean checkValidString(String s) {
        char[] temp=s.toCharArray();
        boolean[][] dp=new boolean[s.length()][s.length()];
        for(int i=0;i<s.length();i++)dp[i][i]=true;
        for(int i=1;i<s.length();i++){
            for(int j=i-1;j>=0;j--){
                if((i-j==1)&&(temp[i]==')'||temp[i]=='*')&&(temp[j]=='('||temp[j]=='*'))dp[j][i]=true;
                else if((temp[i]==')'||temp[i]=='*')&&(temp[j]=='('||temp[j]=='*'))
                    dp[j][i]=dp[j+1][i-1]&&true;
                else dp[j][i]=false;
            }
        }
        StringBuffer stringBuffer=new StringBuffer();
        stringBuffer.append("a");
//        stringBuffer.deleteCharAt(stringBuffer.length())
        ArrayList<Integer> list=new ArrayList<>();
         Set<Integer> set =new HashSet<>();

        return dp[0][s.length()-1];

    }
}
